//队列的链式存储结构，其实就是线性表的单链表
#include<stdio.h>
#include<stdlib.h>

typedef char DataType;
// 链队的结点结构
typedef struct QNode
{
    DataType data;      
    struct QNode *next; 
}QNode;
// 链队的头尾指针
typedef struct 
{
    QNode *rear;    // 链队尾指针
    QNode *front;   // 链队头指针
}LinkQueue;

// 初始化
void InitQueue(LinkQueue **LQ)
{
    // 链队的头指针和尾指针都指向头结点（为头结点分配空间）
    (*LQ)->front = (*LQ)->rear = (QNode *)malloc(sizeof(QNode));
    (*LQ)->front->next = NULL;
    printf("队列已初始化!\n");
}

// 入队
//在链表的尾部
void EnQueue(LinkQueue *LQ)
{
    DataType x;
    fflush(stdin);      //刷新流 stream 的输出缓冲区
    printf("请输入入队数据:");
    scanf("%c", &x);

    // 创建新结点
    QNode *s = (QNode *)malloc(sizeof(QNode));
    s->data = x;
    s->next = NULL;

    // 尾节点后连接新结点s 
    LQ->rear->next = s;
    // 链队的尾指针指向新结点s
    LQ->rear = s;
    printf("入队:%c\n", LQ->rear->data);
}

// 出队
//从链表的头部进行
void DeQueue(LinkQueue *LQ)
{
    if (LQ->front == LQ->rear)
    {
        printf("队列为空!\n");
    }
    else
    {
        // 获取队头结点（头结点指向的第一个结点）
        QNode *p = LQ->front->next;
        // 头结点指向第二个结点
        LQ->front->next = p->next;
        // 删除最后一个结点时，链队尾指针需要指向头指针
        if (p == LQ->rear)
        {
            LQ->rear = LQ->front;
        }
        printf("出队:%c\n", p->data);
        // 销毁结点
        free(p);
    }
}

// 遍历队列序列
void Display(LinkQueue *LQ)
{
    QNode *p = LQ->front;
    printf("队列: 队头[ ");
    while (p != LQ->rear)
    {
        p = p->next;
        printf("%c ", p->data);
    }
    printf("]队尾\n");
}

// 取队头元素
void GetQueueHead(LinkQueue *LQ)
{
    if (LQ->front == LQ->rear)
    {
        printf("队列为空!\n");
    }
    else
    {
        QNode *p = LQ->front->next;
        printf("队头:%c\n", p->data);
    }
}

// 取队尾元素
void GetQueueTail(LinkQueue *LQ)
{
    if (LQ->front == LQ->rear)
    {
        printf("队列为空!\n");
    }
    else
    {
        QNode *p = LQ->rear;
        printf("队尾:%c\n", p->data);
    }
}

// 求队列长度
void GetLength(LinkQueue *LQ)
{
    int len;
    QNode *p = LQ->front;
    while (p != LQ->rear)
    {
        p = p->next;
        len++;
    }
    printf("队列长度 = %d\n", len);
}


int main()
{
    int k;
    LinkQueue *LQ;
    InitQueue(LinkQueue**LQ);
    EnQueue(LinkQueue*LQ);      
    DeQueue(LinkQueue*LQ);      
    Display(LinkQueue*LQ);      
    GetQueueHead(LinkQueue*LQ); 
    GetQueueTail(LinkQueue*LQ); 
    GetLength(LinkQueue*LQ);
    system("pause");
    return 0;
}